package codingforgreat.lchot150;

import java.util.*;

public class Lc127 {
    //深度遍历无优化版本
    public int ladderLength1(String beginWord, String endWord, List<String> wordList) {
        wordList.add(beginWord);
        HashMap<String,ArrayList<String>> nexts = getNexts(wordList);
        Queue<String> que = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        que.add(beginWord);
        visited.add(beginWord);
        HashMap<String,Integer> distance = new HashMap<>();
        distance.put(beginWord,1);
        while(!que.isEmpty()){
            String cur = que.poll();
            Integer dis = distance.get(cur);
            for(String next : nexts.get(cur)){
                if(next.equals(endWord)){
                    return dis + 1;
                }else{
                    if(!visited.contains(next)){
                        que.add(next);
                        visited.add(next);
                        distance.put(next,dis + 1);
                    }
                }
            }
        }
        return 0;

    }
    public HashMap<String,ArrayList<String>> getNexts(List<String> list){
        HashSet<String> set = new HashSet(list);
        HashMap<String,ArrayList<String>> res = new HashMap<>();
        for(int i = 0;i < list.size();i++){
            res.put(list.get(i),getNext(list.get(i),set));
        }
        return res;
    }
    public ArrayList<String> getNext(String cur,HashSet<String> set){
        ArrayList<String> res = new ArrayList<>();
        char[] ch = cur.toCharArray();
        for(int i = 0;i < ch.length;i++){
            for(char c = 'a';c <= 'z';c++){
                if(ch[i] != c){
                    char tmp = ch[i];
                    ch[i] = c;
                    if(set.contains(String.valueOf(ch))){
                        res.add(String.valueOf(ch));
                    }
                    ch[i] = tmp;
                }
            }
        }
        return res;
    }
    //深度遍历优化版本
    public  int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> set = new HashSet(wordList);
        if(!set.contains(endWord)){
            return 0;
        }
        HashSet<String> start = new HashSet<>();
        HashSet<String> end = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        start.add(beginWord);
        end.add(endWord);
        //visited.add(start);
        for(int len = 2;!start.isEmpty();len++){
            HashSet<String> next = new HashSet<>();
            for(String w : start){

                for(int j = 0;j < w.length();j++){
                    char[] ch = w.toCharArray();
                    for(char c = 'a' ;c <= 'z';c++){
                        if(ch[j] != c){
                            char tmp = ch[j];
                            ch[j] = c;
                            if(end.contains(String.valueOf(ch))){
                                return len;
                            }
                            if(set.contains(String.valueOf(ch)) && !visited.contains(String.valueOf(ch))){
                                next.add(String.valueOf(ch));
                                visited.add(String.valueOf(ch));
                            }
                        }
                    }
                }
            }
            start = next.size() <= end.size() ? next : end;
            end = start == next ? end : next;
        }
        return 0;
    }
}
